package leetcode.stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class SingleStack2 {
    public static int[][] getNearLess(int[] arr){
        int[][] res=new int[arr.length][2];
        Stack<List<Integer>> stack = new Stack<>();
        for (int i = 0; i <arr.length ; i++) {
            while (stack!=null && arr[stack.peek().get(0)]>arr[i]){
                List<Integer> popIs =stack.pop();
                int leftLessIndex = stack.isEmpty()?-1:stack.peek().get(stack.peek().size()-1);
                for (Integer popi:popIs) {
                    res[popi][0] = leftLessIndex;
                    res[popi][1] = i;
                }
            }
            if (!stack.isEmpty() && arr[stack.peek().get(0)]==arr[i]){
                stack.peek().add(Integer.valueOf(i));
            }else {
                List<Integer> list = new ArrayList<>();
                list.add(i);
                stack.push(list);
            }
        }
        while (!stack.isEmpty()){
            List<Integer> popIs =stack.pop();
            int leftLessIndex = stack.isEmpty()?-1:stack.peek().get(stack.peek().size()-1);
            for (Integer popi:popIs) {
                res[popi][0] = leftLessIndex;
                res[popi][1] = -1;
            }
        }
        return res;
    }
}
